package sort.seniorSort;

import sort.template;

import java.util.Arrays;

import static sort.SortCompare.getArray;

public class MergeBU extends template {
    private static Comparable[] aux;
    public static void sort(Comparable[] a){
        int N = a.length;
        aux = new Comparable[N];
        for (int sz=1; sz<N; sz*=2){  //sz表示的是
            for (int lo=0; lo<N-sz; lo = lo+sz*2){
                merge(a, lo, lo+sz-1, Math.min(lo+2*sz-1, N-1));
            }
        }
    }

    private static void merge(Comparable[] a, int lo, int mid, int hi){
        int i=lo;
        int j=mid+1;
        for (int k=lo; k<=hi; k++){
            aux[k] = a[k];
        }
        for (int k=lo; k<=hi; k++){
            if (i>mid) a[k] = aux[j++];
            else if (j>hi) a[k] = aux[i++];
            else if (less(aux[i], aux[j])) a[k] = aux[i++];
            else a[k] = aux[j++];
        }
    }

    public static void main(String[] args) {
        Comparable[] array = getArray(100);
        System.out.println("排序之前的数组："+ Arrays.asList(array));
        sort(array);
        System.out.println("排序之后的数组："+Arrays.asList(array));
        System.out.println(isSorted(array));
    }
}
